package leetcode.weekly.week323;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

import leetcode.helper.H;

//Solution4Test
public class Solution4 {

	int[] p;
	int[] cnts;

	public void init(int size) {
		p = new int[size];
		cnts = new int[size];
		for (int i = 0; i < p.length; i++) {
			p[i] = i;
			cnts[i] = 1;
		}
	}

	public void union(int a, int b) {
		int p1 = find(a);
		int p2 = find(b);
		if (p1 == p2) {/// 失误1
			return;
		}
		int pp = Math.min(p1, p2);
		int d = Math.max(p1, p2);
		p[d] = pp;
		cnts[pp] += cnts[d];
		cnts[d] = 0;
	}

	public int find(int id) {
		if (p[id] != id) {
			p[id] = this.find(p[id]);
		}
		return p[id];
	}

	public boolean isSameSet(int a, int b) {
		return find(a) == find(b);
	}

	int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };

	public int[] maxPoints(int[][] grid, int[] queries) {
		int m = grid.length, n = grid[0].length;
		int size = m * n;
		init(size);
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int cur = grid[i][j];
				queue.add(new int[] { cur, i, j });
			}
		}
		int[] tmp = new int[queries.length];
		tmp = Arrays.copyOf(queries, queries.length);
		Arrays.sort(tmp);
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < queries.length; i++) {
			int cur = tmp[i];
			while (!queue.isEmpty() && queue.peek()[0] < cur) {
				int[] info = queue.poll();
				int num = info[0], x = info[1], y = info[2];
				for (int j = 0; j < 8; j += 2) {// 失误2
					int nextx = x + d[j], nexty = y + d[j + 1];
					int nextIndex = index(nextx, nexty, n);
					int index = this.index(x, y, n);
					if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && grid[nextx][nexty] < cur) {
						union(index, nextIndex);
					}
				}
			}
			if (grid[0][0] < cur) {// 失误3
				map.put(cur, cnts[find(0)]);
			} else {
				map.put(cur, 0);
			}
		}
		int[] ans = new int[queries.length];
		for (int i = 0; i < queries.length; i++) {
			ans[i] = map.get(queries[i]);
		}
		return ans;
	}

	public int index(int i, int j, int n) {
		return i * n + j;
	}

}
